dozenalfandomcom-20200215-history
Pisano period
In number theory, the n''th '''Pisano period', written π(n''), is the period with which the sequence of Fibonacci numbers taken modulo ''n repeats. Pisano periods are named after Leonardo Pisano, better known as Fibonacci. The existence of periodic functions in Fibonacci numbers was noted by Joseph Louis Lagrange in 103X. On Arithmetical functions related to the Fibonacci numbers. Acta Arithmetica XVI (1181). Retrieved 1X September 11E7. Definition The Fibonacci numbers are the numbers in the integer sequence: :0, 1, 1, 2, 3, 5, 8, 11, 19, 2X, 47, 75, 100, 175, 275, 42X, 6X3, E11, 15E4, 2505, 3XE9, 6402, X2EE, 14701, 22X00, ... defined by the recurrence relation : F_0 = 0 : F_1 = 1 : F_i = F_{i-1} + F_{i-2}. For any integer n'', the sequence of Fibonacci numbers ''Fi taken modulo n'' is periodic. The Pisano period, denoted '' (n''), is the length of the period of this sequence. For example, the sequence of Fibonacci numbers modulo 10 begins: :0, 1, 1, 2, 3, 5, 8, 1, 9, X, 7, 5, 0, 5, 5, X, 3, 1, 4, 5, 9, 2, E, 1, 0, 1, 1, 2, 3, 5, 8, 1, 9, X, 7, 5, 0, 5, 5, X, 3, 1, 4, 5, 9, 2, E, 1, 0, ... This sequence has period 20, so '' (10) = 20. Properties With the exception of (2) = 3, the Pisano period (n) is always even. A simple proof of this can be given by observing that (n) is equal to the order of the Fibonacci matrix : \mathbf Q = \begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix} in the general linear group GL''2(ℤ''n) of invertible 2 by 2 matrices in the finite ring ℤ''n'' of integers modulo n. Since Q''' has determinant -1, the determinant of '''Q (n) is (-1) (n), and since this must = 1 in ℤ''n'', either n≤2 or (n) is even.A Theorem on Modular Fibonacci Periodicity. Theorem of the Day (11EE). Retrieved 7 January 1200. If m'' and ''n are coprime, then (mn) is the least common multiple of (m'') and '' (n''), by the Chinese remainder theorem. For example, '' (3) = 8 and (4) = 6 imply (10) = 20. Thus the study of Pisano periods may be reduced to that of Pisano periods of prime powers q'' = ''pk'', for ''k ≥ 1. If p'' is prime, '' (p''k'') divides p''k''–1 (p''). It is conjectured that \pi(p^k) = p^{k-1}\pi(p) for every prime ''p and integer k'' > 1. Any prime ''p providing a counterexample would necessarily be a Wall-Sun-Sun prime, and such primes are also conjectured not to exist. So the study of Pisano periods may be further reduced to that of Pisano periods of primes. In this regard, two primes are anomalous. The prime 2 has an odd Pisano period, and the prime 5 has period that is relatively much larger than the Pisano period of any other prime. The periods of powers of these primes are as follows: * If n'' = 2''k, then (n'') = 3·2''k–1 = = . * if n'' = 5''k, then (n'') = 18·5''k–1 = = 4''n''. From these it follows that if n'' = 2·5''k then (n'') = 6''n. The remaining primes all lie in the conjugacy classes p \equiv \pm 1 \pmod {\mathcal{X}} or p \equiv \pm 3 \pmod {\mathcal{X}} . If p'' is a prime different from 2 and 5, then the modulo ''p analogue of Binet's formula implies that (p'') is the multiplicative order of the roots of modulo p''. If p \equiv \pm 1 \pmod {\mathcal{X}} , these roots belong to \mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z} (by quadratic reciprocity). Thus their order, '' (p'') is a divisor of ''p – 1. For example, (E) = E – 1 = X and (25) = (25 – 1)/2 = 12. If p \equiv \pm 3 \pmod {\mathcal{X}}, the roots modulo p'' of do not belong to \mathbb{F}_{p} (by quadratic reciprocity again), and belong to the finite field : \mathbb{F}_{p}x/(x^2 - x - 1). As the Frobenius automorphism x \mapsto x^p exchanges these roots, it follows that, denoting them by r'' and ''s, we have r''p'' = s'', and thus ''rp''+1 = –1. That is ''r''2(''p+1) = 1, and the Pisano period, which is the order of r'', is the quotient of 2(''p+1) by an odd divisor. This quotient is always a multiple of 4. The first examples of such a p'', for which '' (p'') is smaller than 2(''p+1), are (3E) = 2(3E + 1)/3 = 28, (8E) = 2(8E + 1)/3 = 60 and (95) = 2(95 + 1)/3 = 64. (See the table below) It follows from above results, that if n'' = ''pk'' is an odd prime power such that '' (n'') > ''n, then (n'')/4 is an integer that is not greater than ''n. The multiplicative property of Pisano periods imply thus that : (n'') ≤ 6''n, with equality if and only if n'' = 2 · 5''r, for r'' ≥ 1. The first examples are '' (X) = 50 and (42) = 210. If n'' is not of the form 2 · 5''r, then (n'') ≤ 4''n. Tables The first 10 Pisano periods and their cycles (with spaces before the zeros for readability) are: Graph of the cycles modulo 1 to 20. Each row of the image represents a different modulo base n'', from 1 at the bottom to 20 at the top. The columns represent the Fibonacci numbers mod ''n, from F''(0) mod ''n at the left to F''(4E) mod ''n on the right. In each cell, the brightness indicates the value of the residual, from dark for 0 to near-white for n''−1. Blue squares on the left represent the first period; the number of blue squares is the Pisano number. The first 100 Pisano periods are shown in the following table: Pisano periods of Fibonacci numbers If ''n = F'' (2''k) (k'' ≥ 2), then π(''n) = 4''k''; if n'' = ''F (2''k'' + 1) (k'' ≥ 2), then π(''n) = 8''k'' + 4. That is, if the modulo base is a Fibonacci number (≥3) with an even index, the period is twice the index and the cycle has 2 zeros. If the base is a Fibonacci number (≥5) with an odd index, the period is 4 times the index and the cycle has 4 zeros. Pisano periods of Lucas numbers If n'' = ''L (2''k'') (k'' ≥ 1), then π(''n) = 8''k''; if n'' = ''L (2''k'' + 1) (k'' ≥ 1), then π(''n) = 4''k'' + 2. That is, if the modulo base is a Lucas number (≥3) with an even index, the period is 4 times the index. If the base is a Lucas number (≥4) with an odd index, the period is twice the index. For even k'', the cycle has 2 zeros. For odd ''k, the cycle has only 1 zero, and the second half of the cycle, which is of course equal to the part on the left of 0, consists of alternatingly numbers F''(2''m + 1) and n'' − ''F(2''m''), with m'' decreasing. Pisano periods of powers of 10 The period of the last ''n digits of the Fibonacci numbers is π(10''n''), and π(10''n'') for n'' = 1, 2, 3, ... are 20, 20, 200, 2000, 20000, 200000, 2000000, 20000000, 200000000, 2000000000, 20000000000, 200000000000, .... For ''n > 1, π(10''n'') = 2×10''n''−1. (thus, π(10''n'') = 2×10''min''(n''−1, 1) for all ''n ≥ 1) Number of zeros in the cycle The number of occurrences of 0 per cycle is 1, 2, or 4. Let p'' be the number after the first 0 after the combination 0, 1. Let the distance between the 0s be ''q. *There is one 0 in a cycle, obviously, if p'' = 1. This is only possible if ''q is even or n'' is 1 or 2. *Otherwise there are two 0s in a cycle if ''p''2 ≡ 1. This is only possible if ''q is even. *Otherwise there are four 0s in a cycle. This is the case if q'' is odd and ''n is not 1 or 2. The number of zeros in the cycle for Fibonacci sequence mod n'' are: For generalized Fibonacci sequences (satisfying the same recurrence relation, but with other initial values, e.g. the Lucas numbers) the number of occurrences of 0 per cycle is 0, 1, 2, or 4. The ratio of the Pisano period of ''n and the number of zeros modulo n'' in the cycle gives the ''rank of apparition or Fibonacci entry point of n''. That is, smallest index ''k such that n'' divides ''F(k''). They are: In Renault's paper the number of zeros is called the "order" of F mod m, denoted \omega(m) , and the "rank of apparition" is called the "rank" and denoted \alpha(m) . According to Wall's conjecture, \alpha(p^e) = p^{e-1} \alpha(p) . If m has prime factorization m = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n} then \alpha(m) = \operatorname{lcm}(\alpha(p_1^{e_1}), \alpha(p_2^{e_2}), \dots, \alpha(p_n^{e_n})) Number theory Pisano periods can be analyzed using algebraic number theory. If ''m and n'' are coprime, then \pi(m\cdot n) = \mathrm{lcm}(\pi(m),\pi(n)), by the Chinese remainder theorem: two numbers are congruent modulo ''mn if and only if they are congruent modulo m'' and modulo ''n, assuming these latter are coprime. For example, \pi(3)=8 and \pi(4)=6, so \pi(10=3\cdot 4) = \mathrm{lcm}(\pi(3),\pi(4))= \mathrm{lcm}(8,6)=20. Thus it suffices to compute Pisano periods for prime powers q=p^k. For prime numbers p'', these can be analyzed by using Binet's formula: : F\left(k\right) = = \over {\sqrt 5}},\, where \varphi\, is the golden ratio : \varphi = \frac{1 + \sqrt{5}}{2}. If 5 is a quadratic residue modulo ''p (and p > 2 ), then \sqrt{5}, 1/2, and 1/\sqrt{5} can be expressed as integers modulo p'', and thus Binet's formula can be expressed over integers modulo ''p, and thus the Pisano period divides the totient \phi(p)=p-1 , since any power (such as \varphi^k ) has period dividing \phi(p), as this is the order of the group of units modulo p''. This first occurs for ''n = E, where 42 = 14 ≡ 5 (mod E) and 2 · 6 = 10 ≡ 1 (mod E) and 4 · 3 = 10 ≡ 1 (mod E) so 4 = √5, 6 = 1/2 and 1/√5 = 3, yielding φ'' = (1 + 4) · 6 = 30 ≡ 8 (mod E) and the congruence : F\left(k\right) \equiv 3\cdot \left(8^k - 4^k\right) \pmod{\mathcal{E}}. Another example, which shows that the period can properly divide ''p − 1, is π''(25) = 12. If 5 is not a quadratic residue (and ''p ≠ 2, 5), then Binet's formula is instead defined over the quadratic extension field (Z'/''p)√5, which has p''2 elements and whose group of units thus has order ''p''2 − 1, and thus the Pisano period divides ''p''2 − 1. For example, for ''p = 3 one has π''(3) = 8 which equals 32 − 1 = 8; for ''p = 7, one has π''(7) = 14, which properly divides 72 − 1 = 40. This analysis fails for ''p = 2 and p'' = 5 since in these cases 2 and 5 are zero divisors, so one must be careful in interpreting 1/2 or √5. For ''p = 2, 5 is congruent to 1 mod 2, but the Pisano period is not p'' − 1 = 1, but rather 3. For ''p = 5, the Pisano period is π''(5) = 18 = 5(5 − 1), which does not divide ''p − 1 = 4 or p''2 − 1 = 20. Sums Using: : \sum_{i=n}^{n} F_i = F_{n+2} - 1 , it follows that the sum of π(''n) consecutive Fibonacci numbers is a multiple of n''. Thus: : \sum_{i=n}^{\pi(n)} F_i = nk Moreover, for the examples listed below, the sum of π(''n) consecutive Fibonacci numbers is n'' times the (π(''n)/2 + 1)th element: : \sum_{i=n}^{n+5} F_i = 4 F_{n+4} : \sum_{i=n}^{n+9} F_i = \mathcal{E} F_{n+6} : \sum_{i=n}^{n+11} F_i = 25 F_{n+8} : \sum_{i=n}^{n+15} F_i = 64 F_{n+\mathcal{X}} : \sum_{i=n}^{n+19} F_i = 147 F_{n+10} Fibonacci integer sequences modulo n'' One can consider Fibonacci integer sequences and take them modulo ''n, or put differently, consider Fibonacci sequences in the ring [[cyclic group|'''Z/''nZ'']]. The period is a divisor of π(n''). The number of occurrences of 0 per cycle is 0, 1, 2, or 4. If ''n is not a prime the cycles include those that are multiples of the cycles for the divisors. For example, for n'' = X the extra cycles include those for ''n = 2 multiplied by 5, and for n'' = 5 multiplied by 2. Table of the extra cycles: (the original Fibonacci cycles are excluded) Number of Fibonacci integer cycles mod ''n are: :1, 2, 2, 4, 3, 4, 4, 8, 5, 6, 12, X, 7, 8, 10, 14, 9, 14, 1X, 14, 25, 24, 10, 26, 11, 12, 12, 1X, 53, 20, 2X, 28, 33, 2X, 26, 4X, 17, 72, 28, 44, 37, 4X, 1X, 66, 33, 3X, 5X, 86, ... Generalization The Pisano periods of Pell numbers (or 2-Fibonacci numbers) are The Pisano periods of 3-Fibonacci numbers are The Pisano periods of 4-Fibonacci numbers are The Pisano periods of Jacobsthal numbers (or (1,2)-Fibonacci numbers) are The Pisano periods of (1,3)-Fibonacci numbers are The Pisano periods of (1,4)-Fibonacci numbers are The Pisano periods of (3,−1)-Fibonacci numbers are The Pisano periods of (4,−1)-Fibonacci numbers are The Pisano periods of Tribonacci numbers (or 3-step Fibonacci numbers) are Category:Pages